#include <string>
#include <stack>

using std::string;
using std::stack;

class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 2 != 0) {
            return false;
        }
        stack<char> stack;
        for (char c : s) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            }
            else {
                if (stack.empty() || (c == ')' && stack.top() != '(') || (c == ']' && stack.top() != '[') || (c == '}' && stack.top() != '{')) {
                    return false;
                }
                else {
                    stack.pop();
                }
            }
        }
        return stack.empty();
    }
};